package leetcode.editor.cn.dsa04_queue;
//写一个 RecentCounter 类来计算特定时间范围内最近的请求。

public class NumberOfRecentCalls933_2 {
    public static void main(String[] args) {
        RecentCounter recentCounter = new NumberOfRecentCalls933_2().new RecentCounter();
        System.out.println(recentCounter.ping(1)); //1
        System.out.println(recentCounter.ping(100)); //2
        System.out.println(recentCounter.ping(3001)); //3
        System.out.println(recentCounter.ping(3002)); //3
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    /**
     * 优化解法：双指针
     * 空间优化：数组的有效请求只有3001个，只需要定义3001容量空间
     */
    class RecentCounter {
        // 1.创建数组，存放所有的请求
        int[] arr = new int[3002];
        // 2.记录起止索引，从0开始
        int start = 0, end = 0;
        public RecentCounter() {
        }

        public int ping(int t) {
            // 3.存放请求后，更新起止索引
            arr[end++] = t;
            end = end == arr.length ? 0 : end; // 越界后，从0开始
            // 从start位置开始，正向查找符合要求的请求次数
            while(arr[start] < t - 3000){
                start++; // 过滤掉所有不符合要求的数据
                start = start == arr.length ? 0 : start;
            }
            // 4.通过end与start差值计算请求次数
            if (start > end) { // 请求次数超过数组容量，发生了溢出
                return arr.length - (start - end);
            }
            // 此时，end为最新一次请求 + 1 的索引
            // start是3000毫秒前的第一次合法请求索引
            return end - start;
        }
    }
    /**
     * Your RecentCounter object will be instantiated and called as such:
     * RecentCounter obj = new RecentCounter();
     * int param_1 = obj.ping(t);
     */
    //leetcode submit region end(Prohibit modification and deletion)
}